1. Field of the Invention
The present invention relates to computer displays. More specifically, the present invention relates to the efficient rendering of line segments on a computer display.
2. The Background
A computer display is made up of rows and columns of pixels. Each pixel may be very small. However, computer display technology has not yet advanced to the point where the pixels are small enough to avoid several limitations encountered when graphics are viewed by the human eye.
Line segments are represented as mathematical equations. Each segment will have a starting point, and ending point, and a slope. While some line segments may be relatively easy to draw on a computer display, such as precisely horizontal or vertical lines, most lines require some degree of approximation in choosing which pixels to illuminate in order to best represent the line segment to a viewer.
FIG. 1 is a diagram illustrating a line segment overlaid on a group of pixels. As can be seen, decisions must be made as to which pixels should be illuminated. For example, in column 2, a decision must be made between pixel 10 and pixel 12.
A common method for determining which pixels to illuminate to best represent a line segment is Bresenhan""s line algorithm. In Bresenham""s approach, for lines with slopes between 0 and 1, pixel positions along a line segment are determined by sampling the line in one-pixel increments. Therefore, the process starts at the starting point 14 and steps to each successive column. At each column, the pixel is chosen whose y value is closest to the line segment.
Starting from the left end-point (x0,y0) of a given line, the process steps to each successive column (x position) and illuminates the pixel whose scan-line y-value is closest to the line segment. FIG. 2 is a diagram illustrating the kth step in this process. Assuming that the pixel at (xk,yk) is to be displayed, the process needs to determine which pixel to plot in column xk+1. The choices are the pixels at positions (Xk+1,Yk) and (xk+1, yk+1).
At sampling position xk+1, the vertical pixel separations from the mathematical line path may be termed d1 and d2. The y coordinate on the mathematical line segment at pixel column position xk+1 is calculated as
xe2x80x83y=m(xk+1)+b
where m=dy/dx
Then
d1=yxe2x88x92yk
d1=m(xk+1)+bxe2x88x92yk
d2=(yk+1)xe2x88x92y
d2=yk+1xe2x88x92m(xk+1)xe2x88x92b
The difference between these two separations is
d1xe2x88x92d2=2m(xk+1)xe2x88x922yk+2bxe2x88x921
The decision parameter pk for the kth step in the line process may be determined by rearranging the equations so that they only involve integer calculations. This may be accomplished by substituting m=xcex94y/xcex94x, where xcex94y and xcex94x are the vertical and horizontal separations of the endpoint positions, and defining:
pk=xcex94x(d1xe2x88x92d2)
xe2x80x83pk=2xcex94yxc2x7xkxe2x88x922/xcex94xxc2x7yk+c
The sign of pk is the same as the sign of d1xe2x88x92d2, since in the present case xcex94x  greater than 0. Parameter c is constant and has the value 2xcex94y+xcex94x (2bxe2x88x921), which is independent of pixel position and will be eliminated in the recursive calculations for pk. If the pixel at yk is closer to the line path than the pixel at yk+1(that is, d1 less than d2), then decision parameter pk is negative. In that case, the lower pixel is illuminated, otherwise the upper pixel is illuminated.
Coordinate changes along the line occur in unit steps in either the x or y directions. Therefore, the values of successive decision parameters can be obtained using incremental integer calculations. At step k+1, the decision parameter is evaluated as
Pk+1=pk+2xcex94yxc2x7Xk+1xe2x88x922xcex94xxc2x7yk+1+C
Subtracting pk=2xcex94yxc2x7xkxe2x88x922/xcex94xxc2x7yk+C from the preceding equation, we have
Pk+1xe2x88x92pk=2xcex94y(xk+1xe2x88x92xk)xe2x88x922xcex94x(yk+1+Yk)
But xk+1=xk+1, so that
Pk+1=pk+2xcex94yxe2x88x922xcex94x(yk+1+yk)
where the term Yk+1+Yk is either 0 or 1, depending on the sign of parameter pk.
This recursive calculation of decision parameters is performed at each integer x position, starting at the left coordinate endpoint of the line. The first parameter, p0, is evaluated at the starting pixel position (x0, y0) and with m evaluated as xcex94y/xcex94x:
p0+2xcex94yxe2x88x92xcex94x
Bresenham""s method may be summarized as follows (for slope value between xe2x88x921 and 1):
1. Begin with starting point (x0, y0)
2. calculate the following constants:
xcex94xxe2x88x92the change in x over the entire line segment
xcex94yxe2x88x92the change in y over the entire line segment
2xcex94y
2xcex94yxe2x88x922xcex94x
3. Calculate the starting value for the decision parameter (p) as
p02xcex94yxe2x88x92xcex94x
4. At each xk along the line segment, starting at k=0, perform the following test: if pk less than 0, the next point to plot is (xk+1, Yk) and
pk+1=pk+2xcex94y
xe2x80x83Otherwise, the next point to plot is (xk+1, yk+1) and
pk +1=pk+2xcex94yxe2x88x922xcex94x
5. Repeat step 4 for each column until the ending point is reached.
In recent years, there has been movement away from powerful mainframe computers to smaller, cheaper, less powerful processors, such as those that may be contained in set-top boxes and hand-held devices. The computation of constants requires a lot of computing power lest the speed of the line drawing suffer. The problem, therefore, with using Bresenham""s method for drawing lines is that it requires the calculation of four different constants. What is needed is a solution for approximating line segments which can be performed with less calculations yet would yield similar results.
A method for rendering a line segment extending in the positive-x direction and positively direction on a computer display given a starting point and an ending point, the starting point having the form (xs, ys) and the ending point having the form (xe, ye). In this method, xcex94x and xcex94y are computed using the formula xcex94x=|xexe2x88x92xs| and xcex94y=|yexe2x88x92ys|, respectively. Then dt(0)=(yf*xcex94x)xe2x88x92(xf*xcex94y) is computed, where xf is the fractional portion of xs and yf is the fractional portion of ys, which allows for more precision. If the line segment extends in the postive-x and positive-y directions, then for each column n containing a portion of said line segment the process: plots said current pixel if dt(n) less than =0.5*xcex94x and plotting the pixel above said current pixel if dt(n) greater than 0.5*xcex94x; moves said current pixel to the right one pixel if dt(n) less than =0.5*xcex94x and moves said pixel to the right and up one pixel if dt(n) greater than 0.5*xcex94x; and corrects dt(n) by computing dt(n)=dt(n)xe2x88x92xcex94x if dt(n) greater than 0.5*xcex94x. After all of these computations have been performed, the process may iterate to the next column by computing dt(n+1)=dt(n)+xcex94y. This method greatly reduces the number of calculations required by the prior art methods, thus producing a faster and more efficient process by which to draw line segments on a computer display.